package pl.enigmatic.math.graph;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

import pl.enigmatic.util.Collections;
import pl.enigmatic.util.Strings;
import pl.enigmatic.util.Transformer;


/**
 * @author reggie_7
 * 
 * @param <B> base node
 * @param <T> has to be the extending class
 */
@SuppressWarnings("unchecked")
public class Tree<B, T extends Tree<B, T>> extends Node<B, T> implements Iterable<Node<B, T>> {

	protected static <B, T extends Tree<B, T>> int setParentChildRelationship(final T parent, final Node<B, T> child, int index) {
		if (child != null && (parent != null || parent != child.getParent())) {// coś do zmiany mamy - dziecko istnieje i jeden z rodziców też
			final T oldParent = child.getParent();
			if (parent == null) {
				child.parent = null;
				oldParent.children.remove(child);
				oldParent.baseChildren.remove(child.getBase());
				index = -1;
				child.depth = 0;
				oldParent.resetHeight();
				child.setRoot(null);
				oldParent.onChildrenChanged(null, child);
			} else {
				if (child instanceof Tree && ((Tree<B, T>) child).isAncestorOf(parent)) { return -1; }
				index = Collections.wrap(parent.children, index);
				if (oldParent == parent && parent.getChildAt(index) == child) { return index; }
				child.parent = parent;
				if (oldParent != null) {
					oldParent.children.remove(child);
					oldParent.baseChildren.remove(child.getBase());
					oldParent.resetHeight();
				}
				parent.children.add(index, child);
				parent.baseChildren.add(index, child.getBase());
				child.depth = parent.getDepth() + 1;
				child.setRoot(parent.getRoot());
				if (child instanceof Tree && ((Tree<B, T>) child).getHeight() >= parent.height) {
					parent.resetHeight(((Tree<B, T>) child).getHeight() + 1);
				} else if (parent.getChildrenCount() == 1) {
					parent.resetHeight(1);
				}
				if (oldParent == parent) {
					parent.onChildrenChanged(child, child);
				} else {
					if (oldParent != null) {
						oldParent.onChildrenChanged(null, child);
					}
					parent.onChildrenChanged(child, null);
				}
			}
			child.onParentChanged(oldParent);
			return index;
		}
		return -1;
	}

	/**
	 * The height of <code>this</code> tree structure. The same as the distance to the farthest descendant.
	 */
	int height = 0;

	/**
	 * The children of <code>this</code> object in the tree structure.
	 */
	final List<Node<B, T>> children = new ArrayList<Node<B, T>>();
	protected final List<B> baseChildren;

	public Tree(final B base, final List<B> baseChildren) {
		super(base);
		setRoot((T) this);
		this.baseChildren = baseChildren;
		baseChildren.clear();
	}

	public Tree(final B base) {
		this(base, new ArrayList<B>());
	}

	public List<B> getBaseChildren() {
		return baseChildren;
	}

	void resetHeight(int newHeight) {
		height = newHeight;
		T t = (T) this;
		while (t != null) {
			t.height = newHeight++;
			t = t.getParent();
		}
	}

	void resetHeight() {
		int h = 0;
		for (final Node<B, T> c : children) {
			int ch = 0;
			if (c instanceof Tree) {
				ch = ((Tree<B, T>) c).height;
			}
			h = Math.max(h, ch);
		}
		resetHeight(h + 1);
	}

	/**
	 * Called when the children collection of <code>this</code> object is modified. The rules are as follows:
	 * <ul>
	 * <li>If the <code>added</code> child is <code>null</code> - the <code>removed</code> child is not <code>null</code> and it indicates that the
	 * operation was only removing the child.</li>
	 * <li>If the <code>removed</code> child is <code>null</code> - the <code>added</code> child is not <code>null</code> and it indicates that the
	 * operation was only adding the child.</li>
	 * <li>If both children are not <code>null</code> - they are both the same object (<code>added == removed</code>) and the operation was changing
	 * the child's index.</li>
	 * </ul>
	 * 
	 * @param added the added child, or <code>null</code>, if the child was removed
	 * @param removed the removed child, or <code>null</code>, if the child was added
	 */
	protected void onChildrenChanged(final Node<B, T> added, final Node<B, T> removed) {};

	@Override
	void setRoot(T root) {
		if (root == null) {
			root = (T) this;
		}
		super.setRoot(root);
		for (final Node<B, T> c : children) {
			c.setRoot(root);
		}
	}

	/**
	 * Adds a new child element to <code>this</code> object. <code>this</code> becomes the parent. If the new <code>child</code> is already a child of
	 * <code>this</code> object it is shifted to the desired position. Nothing happens if the <code>child</code> is <code>null</code>, or the
	 * <code>child</code> is an ancestor of <code>this</code> object. The <code>index</code> will be wrapped.
	 * 
	 * @param child the child object to add to <code>this</code> object
	 * @param index the position the new <code>child</code> will occupy in <code>this</code> object's children collection
	 * @return the index of the added <code>child</code> or <code>-1</code>, if <code>child</code> was not added
	 */
	public int addChild(final Node<B, T> child, final int index) {
		return setParentChildRelationship((T) this, child, index);
	}

	/**
	 * Adds a new child element to <code>this</code> object. <code>this</code> becomes the parent. If the new <code>child</code> is already a child of
	 * <code>this</code> object then it is shifted to the end of the collection. Nothing happens if the <code>child</code> is <code>null</code>, or
	 * the <code>child</code> is an ancestor of <code>this</code> object.
	 * 
	 * @param child the child object to add to <code>this</code> object
	 * @return the index of the added <code>child</code> or <code>-1</code>, if nothing changed
	 * @see Tree#addChild(Tree, int)
	 */
	public int addChild(final Node<B, T> child) {
		return addChild(child, getChildrenCount());
	}

	/**
	 * Removes the parent-child relationship, if the <code>child</code> object is in fact a child of <code>this</code> object.
	 * 
	 * @param child the child object to remove from <code>this</code> object
	 */
	public boolean removeChild(final Node<B, T> child) {
		if (child != null && children.contains(child)) {
			child.setParent(null);
			return true;
		}
		return false;
	}

	/**
	 * Removes the parent-child relationship, if the <code>index</code> object represents in fact a child of <code>this</code> object. The
	 * <code>index</code> will be wrapped.
	 * 
	 * @param index the index of a child object to remove from <code>this</code> object
	 */
	public Node<B, T> removeChildAt(final int index) {
		final Node<B, T> removed = getChildAt(index);
		removeChild(removed);
		return removed;
	}

	/** Removes all the children from <code>this</code> object. */
	public void removeAll() {
		while (hasChildren()) {
			removeChildAt(0);
		}
	}

	public boolean isRoot() {
		return getRoot() == this;
	}

	public boolean nonRoot() {
		return getRoot() != this;
	}

	public boolean hasChildren() {
		return getChildrenCount() > 0;
	}

	/** @return an iterator over the vector of children objects */
	public Iterator<Node<B, T>> iterator() {
		return new Iterator<Node<B, T>>() {

			private int next = 0;
			private Node<B, T> current = null;

			@Override
			public boolean hasNext() {
				return next < children.size();
			}

			@Override
			public Node<B, T> next() {
				return current = children.get(next++);
			}

			@Override
			public void remove() {
				removeChild(current);
				next--;
				current = null;
			}
		};
	}

	/** @return the number of child elements for <code>this</code> object */
	public int getChildrenCount() {
		return children.size();
	}

	/**
	 * @param index the position of the child to be retrieved.
	 * @return the child at the specified index position.
	 */
	public Node<B, T> getChildAt(final int index) {
		return children.get(index);
	}

	public boolean containsChild(final Node<B, T> child) {
		return children.contains(child);
	}

	/**
	 * @param child the child that we want to find a position of
	 * @return the position of the <code>child</code> or <code>-1</code>, if this does not contain the specified <code>child</code>
	 * @see Vector#indexOf(Object)
	 */
	public int getChildPosition(final Node<B, T> child) {
		return children.indexOf(child);
	}

	public int setChildPosition(final Node<B, T> child, final int index) {
		return addChild(child, index);
	}

	/**
	 * @return the height
	 */
	public int getHeight() {
		return height;
	}

	public int getIndexOf(final Node<B, T> child) {
		return isRoot() ? -1 : children.indexOf(child);
	}

	public int getAllDescendantsCount() {
		int res = getChildrenCount();
		final Iterator<Node<B, T>> i = iterator();
		while (i.hasNext()) {
			final Node<B, T> child = i.next();
			if (child instanceof Tree) {
				res += ((Tree<B, T>) child).getAllDescendantsCount();
			} else {
				res++;
			}
		}
		return res;
	}

	/**
	 * Determines whether <code>this</code> object is an ancestor of the <code>descendant</code> object.
	 * 
	 * @param descendant object to check the relation on
	 * @return <code>true</code> if <code>this</code> object is an ancestor of the <code>descendant</code> object, otherwise - <code>false</code>
	 */
	public boolean isAncestorOf(final Node<B, T> descendant) {
		if (descendant == this) { return true; }
		if (descendant != null && descendant.getDepth() >= getDepth()) {
			T p = descendant.getParent();
			while (p != null) {
				if (p == this) { return true; }
				p = p.getParent();
			}
		}
		return false;
	}

	public String toIntendatedString(final Transformer<T, String> tree, final Transformer<Node<B, T>, String> leaf) {
		String res = tree.transform((T) this);
		final Iterator<Node<B, T>> i = iterator();
		while (i.hasNext()) {
			final Node<B, T> child = i.next();
			if (child instanceof Tree) {
				for (final String line : ((Tree<B, T>) child).toIntendatedString(tree, leaf).split("\n")) {
					res += "\n\t" + line;
				}
			} else {
				res += "\n" + Strings.repeat("\t", child.getDepth()) + leaf.transform(child);
			}
		}
		return res;
	}

	/**
	 * Creates simple String representation of this tree with its children. It uses {@link Tree#toString()} to create simple representation on each
	 * level (overriding {@link Tree#toString()} gives the possibility to add new properties to the representation).
	 * 
	 * @return pretty indentated tree of simple Strings representing this tree object
	 */
	public String toIntendatedString() {
		return toIntendatedString(new Transformer<T, String>() {

			@Override
			public String transform(final T src) {
				return src.toString();
			}
		}, new Transformer<Node<B, T>, String>() {

			@Override
			public String transform(final Node<B, T> src) {
				return src.toString();
			}
		});
	}

	public String toIntendatedBaseString() {
		return toIntendatedString(new Transformer<T, String>() {

			@Override
			public String transform(final T src) {
				final B base = src.getBase();
				return base == null ? "null" : base.toString();
			}
		}, new Transformer<Node<B, T>, String>() {

			@Override
			public String transform(final Node<B, T> src) {
				final B base = src.getBase();
				return base == null ? "null" : base.toString();
			}
		});
	}

	public boolean isLeaf() {
		return getChildrenCount() == 0;
	}

	public Set<Node<B, T>> getLeafs(final Set<Node<B, T>> set) {
		if (isLeaf()) {
			set.add(this);
		} else {
			for (final Node<B, T> child : children) {
				if (child instanceof Tree) {
					((Tree<B, T>) child).getLeafs(set);
				} else {
					set.add(child);
				}
			}
		}
		return set;
	}

	public Set<Node<B, T>> getLeafs() {
		return getLeafs(new HashSet<Node<B, T>>());
	}

	public Set<Node<B, T>> getChildrenAtDepth(final int depth) {
		final Set<Node<B, T>> res = new HashSet<Node<B, T>>();
		if (depth >= 0 && depth <= height) {
			if (depth == 0) {
				res.add(this);
			} else if (depth == 1) {
				res.addAll(children);
			} else {
				for (final Node<B, T> c : children) {
					if (c instanceof Tree) {
						res.addAll(((Tree<B, T>) c).getChildrenAtDepth(depth - 1));
					} else if (c.getDepth() == depth) {
						res.add(c);
					}
				}
			}
		}
		return res;
	}

	public Node<B, T> findChildSatisfying(final Node.Condition<B, T> condition) {
		for (final Node<B, T> c : children) {
			if (condition.isSatisfied(c)) { return c; }
		}
		return null;
	}

	public Set<Node<B, T>> findAllChildrenSatisfying(final Node.Condition<B, T> condition) {
		final Set<Node<B, T>> set = new HashSet<Node<B, T>>();
		for (final Node<B, T> c : children) {
			if (condition.isSatisfied(c)) {
				set.add(c);
			}
		}
		return set;
	}

	public Node<B, T> findDescendantSatisfying(final Node.Condition<B, T> condition) {
		for (final Node<B, T> c : children) {
			if (condition.isSatisfied(c)) { return c; }
		}
		for (final Node<B, T> c : children) {
			if (c instanceof Tree) {
				final Node<B, T> res = ((Tree<B, T>) c).findDescendantSatisfying(condition);
				if (res != null) { return res; }
			}
		}
		return null;
	}

	public Set<Node<B, T>> findAllDescendantsSatisfying(final Node.Condition<B, T> condition) {
		final Set<Node<B, T>> set = new HashSet<Node<B, T>>();
		for (final Node<B, T> c : children) {
			if (condition.isSatisfied(c)) {
				set.add(c);
			}
			if (c instanceof Tree) {
				set.addAll(((Tree<B, T>) c).findAllDescendantsSatisfying(condition));
			}
		}
		return set;
	}

	public static interface Condition<B, T extends Tree<B, T>> {

		public boolean isSatisfied(T node);
	}

	public static class SimpleRepresentation<B, T extends Tree<B, T>> extends ArrayList<Object> {

		/***/
		private static final long serialVersionUID = 1L;
		protected final B base;

		public SimpleRepresentation(final T tree) {
			base = tree.getBase();
			for (final Node<B, T> t : tree.children) {
				if (t instanceof Tree) {
					add(new SimpleRepresentation<B, T>((T) t));
				} else {
					add(t);
				}
			}
		}

		@Override
		public String toString() {
			return base.toString();
		}
	}

	public SimpleRepresentation<B, T> getSimpleRepresentation() {
		return new SimpleRepresentation<B, T>((T) this);
	}
}
